# ifndef _GRAPH_H_
# define _GRAPH_H_

#include<iostream>
#include<stdlib.h>

// 考虑到溢出问题，不应该设置为最大值
# define INFINITY       0x1fffffff
# define MAX_VEX_NUM    20

typedef enum {DG, DN, UDG, UDN} graphKind;

// 栈结构
typedef struct {
    int top;
    int bottom;
    int len;
    int elems[MAX_VEX_NUM];
}stack, pathMatrix[MAX_VEX_NUM];

// 队列结构
typedef struct {
    int head;
    int tail;
    int elems[MAX_VEX_NUM];
}queue;

// 临接矩阵中的边节点
typedef struct {
    int adj;
    char *  info;
}arcCell, adjMatrix[MAX_VEX_NUM][MAX_VEX_NUM];

// 临接矩阵
typedef struct {
    int vexs[MAX_VEX_NUM];
    adjMatrix arcs;
    int vex_num;
    int arc_num;
    graphKind kind;
}matGraph;

// 临接表中的边节点
typedef struct _arcNode{
    int target_vex;
    int weight;
    _arcNode *next_arc;
    char *  info;
}arcNode;

// 临接表中的数据节点
typedef struct _vexNode{
    int vex_value;
    arcNode * first_arc;
}vexNode, vexList[MAX_VEX_NUM+1];

// 临接表存储结构
typedef struct{
    vexList vexs;
    int vex_num;
    int arc_num;
    graphKind kind;
}alGraph;

// Primer算法辅助数组
typedef struct {
    int adj_vex;
    int low_cost;
}closeEdge[MAX_VEX_NUM];

typedef struct {
    int init_vex;
    int dest_vex;
    int weight;
}Edge, Edges[MAX_VEX_NUM];

// Kruskal 辅助数组
typedef struct {
    int vex;
    int sign;
}assist[MAX_VEX_NUM];

// Djikstra 辅助距离数组
typedef struct table{
    int vex;
    int weight;
}sPathTable[MAX_VEX_NUM];

// stack
bool initStack(stack & s);

bool popStack(stack & s, int & elem);

bool pushStack(stack & s, int elem);

// queue
bool initQueue(queue & q);

bool inQueue(queue & q, int elem);

bool deQueue(queue & q, int & elem);

// 创建临接矩阵图结构
bool createMGraph(matGraph & graph);

// 创建临接表图结构
bool createALGraph(alGraph & graph);

// 临接表 -- 返回节点的第一个边
arcNode * getFisrtAdj(alGraph & graph, int vex);

//arcCell * getFisrtAdj(matGraph & graph, int vex);
// 临接表 -- 返回当前边的下一条
int getNextAdj(matGraph & graph, int vex,  int adj);

// 深度优先遍历
bool dfsTraverse(alGraph & graph, bool(* visit)(vexNode & vex));

// 递归搜索
bool dfsNode(alGraph & graph, int vex);

// 有一点问题，不影响程序运行。返回的时候会会触发栈保护机制，暂时未定位到具体地点，编译时添加选项-fno-stack-protector暂时避免了报错
bool bfsTraverse(alGraph & graph, bool(* visit)(vexNode & vex));

// 利用深度优先搜索，判断是否连通图
bool isConnected(matGraph & graph);
bool isConnected(alGraph & graph);

// Prime
bool miniSpanTreePrime(matGraph & graph, int start);

int miniEdge(closeEdge & edges, matGraph & graph);

// Kruskal
bool sortEdges(matGraph & graph, Edges & edges);

bool miniSpanTreeKruskal(matGraph & graph);

// Dijkstra
bool shortPathDijkstra(matGraph & graph, pathMatrix & path, sPathTable & d_table, const int init_vex);

bool putPathDijkstra(matGraph & graph, pathMatrix & path);

// Floyd
typedef bool fPath[MAX_VEX_NUM][MAX_VEX_NUM][MAX_VEX_NUM];
typedef int dMatrix[MAX_VEX_NUM][MAX_VEX_NUM];

bool shortPathFloyd(matGraph & graph, fPath & path, dMatrix & dist);

bool putPathFloyd(matGraph & graph, fPath & path, int start, int end);

bool getPathFloyd(fPath & path, int start, int end, int vex_num);

# endif // _GRAPH_H_